#include <iostream>
#include <vector>
using namespace std;

//bool cmpfunc(vector<int>::iterator a1, 
//        vector<int>::iterator a2)

template <typename T>
bool cmpfunc(T *a1, T *a2)
{
    if (*a1 < *a2)
        return true;
    return false;
}
/*
void quickSort(vector<int>::iterator head, 
        vector<int>::iterator tail, 
        bool (*func)(vector<int>::iterator a1, vector<int>::iterator a2))
*/
template <typename T>
void quickSort(T *head, T* tail, bool (*func)(T*, T*))
{
    int i, j;
    int middle;
    int l,r;
    int tmp;
    int *pointer = head;
    int *dir = &r;
    if (head >= tail)
        return ;
    for (i = 0, l = 0, r = tail-head; i < (tail-head+1); i++) {
        
        if (dir == &r) {
            if (func(head + r, pointer)) {
                {
                    tmp = *pointer;
                    *pointer = head[r];
                    head[r] = tmp;
                }
                pointer = head + r;
                dir= &l;
                (*dir) ++;
            } else {
                (*dir) --;
            }
        } else {
            if (func(pointer, head + l)) {
                {
                    tmp = *pointer;
                    *pointer = head[l];
                    head[l] = tmp;
                }
                pointer = head + l;
                dir= &r;
                (*dir) --;
            } else {
                (*dir) ++;
            }
        }

        if (l>=r) {
            middle = (l+r)/2;
            break;
        }
    }
    quickSort(head, head + middle - 1, func);
    quickSort(head + middle + 1, tail, func);
}

int main(int argc, const char *argv[])
{
    //vector<int> s_v = {3,1,6,4,8,7,5,9,2};
    vector<int> s_v = {3,2,6,4,1,7,5,9,8};
    quickSort(static_cast<int*>(&*(s_v.begin())), static_cast<int*>(&*(s_v.end() - 1)), &cmpfunc);
    int i;
    for (i = 0; i < s_v.size(); i++) {
        cout << s_v[i] << endl;
    }

    return 0;
}
